package com.example.leetcode.prcatice;

import java.util.Stack;

public class Test316 {

    // cbacdcbc -> acdb
    public String removeDuplicateLetters(String s) {
        Stack<Character> stack = new Stack<>();
        boolean[] use = new boolean[26];
        StringBuilder sb = new StringBuilder();
        for (int i = 0;i<s.length();i++){
            int index = s.charAt(i) - 97;
            if (use[index]) continue;
            // 插入之前，和之前的元素比较一下大小
            // 如果字典序比前面的小，pop 前面的元素
            while (!stack.isEmpty() && stack.peek() > s.charAt(i)) {
                // 弹出栈顶元素，并把该元素标记为不在栈中
                use[stack.pop()-97] = false;
            }

            stack.push(s.charAt(i));
            use[index] = true;
        }
        while (!stack.isEmpty()){
            sb.append(stack.pop());
        }
        return sb.reverse().toString();
    }
}


class Demo316{
  public static void main(String[] args) {
     String s = "cbacdcbc";
     Test316 t = new Test316();
     System.out.println(t.removeDuplicateLetters(s));

  }
}
